package com.nl.list;

import com.nl.list.LinkedList.Node;

public class MergeSortedLinkedList {

	public static <T extends Comparable<T>> LinkedList<T> merge(
			LinkedList<T> list1, LinkedList<T> list2) {

		if (list1 == null) {
			return list2;
		}
		if (list2 == null) {
			return list1;
		}
		Node<T> p1 = list1.phead;
		Node<T> p2 = list2.phead;
		Node<T> phead = null;
		Node<T> toBeInsert = null;
		Node<T> node = null;
		while (p1 != null && p2 != null) {
			if (p1.value.compareTo(p2.value) > 0) {
				toBeInsert = p2;
				p2 = p2.next;
			} else {
				toBeInsert = p1;
				p1 = p1.next;
			}

			if (node == null) {
				phead = node = toBeInsert;
			} else {
				node.next = toBeInsert;
				toBeInsert.next = null;
				node = toBeInsert;
			}
		}
		if (p1 != null) {
			node.next = p1;
		}

		if (p2 != null) {
			node.next = p2;
		}
		LinkedList<T> list = new LinkedList<T>();
		list.phead = phead;
		return list;
	}
	
	public static <T extends Comparable<T>> Node<T> mergeRecursively(Node<T> phead1,Node<T> phead2){
		if(phead1==null){
			return phead2;
		}
		if(phead2==null){
			return phead1;
		}
		
		Node<T> phead =null;
		
		if(phead1.value.compareTo(phead2.value)>0){
			phead = phead2;
			phead.next = mergeRecursively(phead1, phead.next);
		}else{
			phead = phead1;
			phead.next = mergeRecursively(phead1.next, phead);
		}

		return phead;
	}

	public static void main(String[] args) {
		LinkedList<Integer> list1 = new LinkedList<Integer>();
		list1.addToTail(1);
		list1.addToTail(3);
		list1.addToTail(5);
		LinkedList<Integer> list2 = new LinkedList<Integer>();
		list2.addToTail(2);
		list2.addToTail(4);
		list2.addToTail(6);
		list2.addToTail(60);

		LinkedList<Integer> list = merge(list1, list2);
		if (list != null && list.phead != null) {
			Node<Integer> node = list.phead;
			while (node != null) {
				System.out.print(node.value + " ");
				node = node.next;
			}
		}
	}
}
